package lru.review5_21;

public class Kmp {
    public  int volientMatch(String s,String p) {
        int length1 = s.length();
        int length2 = p.length();
        int i=0;
        int j=0;
        while (i<length1&&j<length2){
            if (s.charAt(i)==p.charAt(j)){
                i++;
                j++;
            }else {
                //  CKG TODO 2023/5/21:　　当不匹配的时候， i　每次向后移动一位　　
                i=i-j+1;
                j=0;
            }
            //  CKG TODO 2023/5/21:  注意这里是等于length2 　　因为j++ 的缘故
            if (j==length2){
                return i-j;
            }
        }
        return -1;
    }


    public static int KMP(String s,String p,int pos) {
        if (s==null||p==null){
            return  -1;
        }
        if (pos<0||pos>=s.length()){
            return -1;
        }

        int length1 = s.length();
        int length2 = p.length();
        int i=pos;
        int j=0;

        int[] next = new int[length2];
        getNext(next,p);


        while (i<length1&&j<length2){
            //  CKG TODO 2023/5/21:  根据昨晚看的文章　　算出每一个位置的最长公共前后缀后向右平移一位　第一位就为－１

            if (j==-1||s.charAt(i)==p.charAt(j)){
                i++;
                j++;
            }else {
//                i=i-j+1;
                j=next[j];
            }
//            if (j==length2){
//                return i-j;
//            }
        }
        //  CKG TODO 2023/5/21: 此处的ｊ的判断跳出了ｗｈｉｌｅ循环
        if (j>=length2){
            return i-j;
        }
        else{
            return -1;
        }

    }


    public static void getNext(int[] next,String p) {
        next[0]=-1;
        next[1]=0;

        int i=2;
        int k=0;
//  CKG TODO 2023/5/21: 很是不理解诶啊
        while (i<next.length){
            if (k==-1||p.charAt(k)==p.charAt(i-1)){
                next[i]=k+1;
                i++;
                k++;
            }else {
                k=next[k];
            }



        }



    }

    public static void main(String[] args) {
        Kmp kmp = new Kmp();
        System.out.println(kmp.volientMatch("BBCABCDABABCDABDABDE", "ABCDABD"));
        System.out.println(Kmp.KMP("BBCABCDABABCDABDABDE", "ABCDABD", 0));
    }





}
